{\rtf1\adeflang1025\ansi\ansicpg10000\uc1\adeff0\deff0\stshfdbch0\stshfloch0\stshfhich0\stshfbi0\deflang1033\deflangfe1033\themelang1033\themelangfe0\themelangcs0{\upr{\fonttbl{\f0\fbidi \fnil\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\f2\fbidi \fnil\fcharset0\fprq2{\*\panose 02070309020205020404}Courier New;}{\f3\fbidi \fnil\fcharset2\fprq2{\*\panose 02000500000000000000}Symbol;}{\f129\fbidi \fnil\fcharset0\fprq2{\*\panose 02000500000000000000}Monaco;}{\flomajor\f31500\fbidi \fnil\fcharset0\fprq2{\*\panose 020b0604020202020204}Arial;}{\fdbmajor\f31501\fbidi \fnil\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\fhimajor\f31502\fbidi \fnil\fcharset0\fprq2{\*\panose 020f0502020204030204}Calibri;}{\fbimajor\f31503\fbidi \fnil\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\flominor\f31504\fbidi \fnil\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\fdbminor\f31505\fbidi \fnil\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\fhiminor\f31506\fbidi \fnil\fcharset0\fprq2{\*\panose 02040503050406030204}Cambria;}{\fbiminor\f31507\fbidi \fnil\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}}{\*\ud{\fonttbl{\f0\fbidi \fnil\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\f2\fbidi \fnil\fcharset0\fprq2{\*\panose 02070309020205020404}Courier New;}{\f3\fbidi \fnil\fcharset2\fprq2{\*\panose 02000500000000000000}Symbol;}{\f129\fbidi \fnil\fcharset0\fprq2{\*\panose 02000500000000000000}Monaco;}{\flomajor\f31500\fbidi \fnil\fcharset0\fprq2{\*\panose 020b0604020202020204}Arial;}{\fdbmajor\f31501\fbidi \fnil\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\fhimajor\f31502\fbidi \fnil\fcharset0\fprq2{\*\panose 020f0502020204030204}Calibri;}{\fbimajor\f31503\fbidi \fnil\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\flominor\f31504\fbidi \fnil\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\fdbminor\f31505\fbidi \fnil\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\fhiminor\f31506\fbidi \fnil\fcharset0\fprq2{\*\panose 02040503050406030204}Cambria;}{\fbiminor\f31507\fbidi \fnil\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}}}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;\red0\green255\blue0;\red255\green0\blue255;\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;\red128\green128\blue0;\red128\green128\blue128;\red192\green192\blue192;}{\*\defchp }{\*\defpap \ql \li0\ri0\widctlpar\wrapdefault\aspalpha\aspnum\faauto\adjustright\rin0\lin0\itap0 }\noqfpromote {\stylesheet{\qj \li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \snext0 Normal;}{\s1\ql \li0\ri0\sb240\sa120\keepn\nowidctlpar\wrapdefault\faauto\outlinelevel0\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs40 \ltrch\fcs0 \b\fs40\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 \slink16 heading 1;}{\s2\ql \li0\ri0\sb240\sa120\keepn\nowidctlpar\wrapdefault\faauto\outlinelevel1\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 \slink17 heading 2;}{\s3\ql \li0\ri0\sb240\sa120\keepn\nowidctlpar\wrapdefault\faauto\outlinelevel2\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 \slink18 heading 3;}{\s4\ql \li0\ri0\sb240\sa120\keepn\nowidctlpar\wrapdefault\faauto\outlinelevel3\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs24 \ltrch\fcs0 \b\fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 \slink19 heading 4;}{\s5\ql \li0\ri0\sb240\sa120\keepn\nowidctlpar\wrapdefault\faauto\outlinelevel4\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs24 \ltrch\fcs0 \b\fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 \slink20 heading 5;}{\s6\ql \li0\ri0\sb240\sa120\keepn\nowidctlpar\wrapdefault\faauto\outlinelevel5\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs24 \ltrch\fcs0 \b\fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 \slink21 heading 6;}{\*\cs10 \additive \ssemihidden Default Paragraph Font;}{\*\ts11\tsrowd\trftsWidthB3\trpaddl108\trpaddr108\trpaddfl3\trpaddft3\trpaddfb3\trpaddfr3\tblind0\tblindtype3\tscellwidthfts0\tsvertalt\tsbrdrt\tsbrdrl\tsbrdrb\tsbrdrr\tsbrdrdgl\tsbrdrdgr\tsbrdrh\tsbrdrv \ql \li0\ri0\widctlpar\wrapdefault\aspalpha\aspnum\faauto\adjustright\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20\alang1033 \ltrch\fcs0 \fs20\lang1033\langfe1033\cgrid\langnp1033\langfenp1033 \snext11 \ssemihidden Normal Table;}{\s15\qc \li0\ri0\sb240\sa120\keepn\nowidctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs40 \ltrch\fcs0 \b\fs40\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 Part;}{\*\cs16 \additive \rtlch\fcs1 \ab\af31503\alang1024 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\kerning32\loch\f31502\hich\af31502\dbch\af31501\noproof \sbasedon10 \slink1 \slocked Heading 1 Char;}{\*\cs17 \additive \rtlch\fcs1 \ab\ai\af31503\alang1024 \ltrch\fcs0 \b\i\fs28\lang1024\langfe1024\loch\f31502\hich\af31502\dbch\af31501\noproof \sbasedon10 \slink2 \slocked \ssemihidden Heading 2 Char;}{\*\cs18 \additive \rtlch\fcs1 \ab\af31503\alang1024 \ltrch\fcs0 \b\fs26\lang1024\langfe1024\loch\f31502\hich\af31502\dbch\af31501\noproof \sbasedon10 \slink3 \slocked \ssemihidden Heading 3 Char;}{\*\cs19 \additive \rtlch\fcs1 \ab\af31507\alang1024 \ltrch\fcs0 \b\fs28\lang1024\langfe1024\loch\f31506\hich\af31506\dbch\af31505\noproof \sbasedon10 \slink4 \slocked \ssemihidden Heading 4 Char;}{\*\cs20 \additive \rtlch\fcs1 \ab\ai\af31507\alang1024 \ltrch\fcs0 \b\i\fs26\lang1024\langfe1024\loch\f31506\hich\af31506\dbch\af31505\noproof \sbasedon10 \slink5 \slocked \ssemihidden Heading 5 Char;}{\*\cs21 \additive \rtlch\fcs1 \ab\af31507\alang1024 \ltrch\fcs0 \b\fs22\lang1024\langfe1024\loch\f31506\hich\af31506\dbch\af31505\noproof \sbasedon10 \slink6 \slocked \ssemihidden Heading 6 Char;}{\s22\qr \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext22 rightpar;}{\s23\qc \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext23 centerpar;}{\s24\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 equation;}{\s25\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 equationNum;}{\s26\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 equationAlign;}{\s27\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 equationAlignNum;}{\s28\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 equationArray;}{\s29\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 equationArrayNum;}{\s30\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 theorem;}{\s31\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 bitmapCenter;}{\s32\qc \li0\ri0\sb240\sa240\nowidctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs36 \ltrch\fcs0 \b\fs36\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext34 \slink33 Title;}{\*\cs33 \additive \rtlch\fcs1 \ab\af31503\alang1024 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\kerning28\loch\f31502\hich\af31502\dbch\af31501\noproof \sbasedon10 \slink32 \slocked Title Char;}{\s34\qc \li0\ri0\sa120\nowidctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 author;}{\s35\ql \li0\ri0\nowidctlpar\tqc\tx4536\tqr\tx9072\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext35 \slink36 footer;}{\*\cs36 \additive \rtlch\fcs1 \af0\alang1024 \ltrch\fcs0 \lang1024\langfe1024\noproof \sbasedon10 \slink35 \slocked \ssemihidden Footer Char;}{\s37\ql \li0\ri0\nowidctlpar\tqc\tx4536\tqr\tx9072\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext37 \slink38 header;}{\*\cs38 \additive \rtlch\fcs1 \af0\alang1024 \ltrch\fcs0 \lang1024\langfe1024\noproof \sbasedon10 \slink37 \slocked \ssemihidden Header Char;}{\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 caption;}{\s40\qc \li0\ri0\sb120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 Figure;}{\s41\qc \li0\ri0\sb120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext41 Table;}{\s42\qc \li0\ri0\sb120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext42 Tabular;}{\s43\qc \li0\ri0\sb120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext43 Tabbing;}{\s44\qj \fi340\li1024\ri1024\widctlpar\wrapdefault\faauto\rin1024\lin1024\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext44 \slink45 Quote;}{\*\cs45 \additive \rtlch\fcs1 \af0\alang1024 \ltrch\fcs0 \lang1024\langfe1024\noproof \sbasedon10 \slink44 \slocked Quote Char;}{\s46\ql \li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af2\afs20 \ltrch\fcs0 \f2\fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \snext46 verbatim;}{\s47\ql \fi-283\li283\ri0\sa120\widctlpar\tx283\wrapdefault\faauto\rin0\lin283\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext47 List;}{\s48\ql \fi-283\li283\ri0\sa120\widctlpar\tx283\wrapdefault\faauto\rin0\lin283\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext48 List 1;}{\s49\qc \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 latex picture;}{\s50\qc \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 subfigure;}{\s51\ql \li0\ri0\sb240\sa120\keepn\nowidctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext52 bibheading;}{\s52\ql \fi-567\li567\ri0\nowidctlpar\wrapdefault\faauto\rin0\lin567\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext52 bibitem;}{\s53\ql \fi-283\li283\ri0\sa120\widctlpar\tx283\wrapdefault\faauto\rin0\lin283\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext53 endnotes;}{\s54\ql \fi-113\li397\ri0\nowidctlpar\wrapdefault\faauto\rin0\lin397\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext54 \slink55 footnote text;}{\*\cs55 \additive \rtlch\fcs1 \af0\alang1024 \ltrch\fcs0 \fs24\lang1024\langfe1024\noproof \sbasedon10 \slink54 \slocked \ssemihidden Footnote Text Char;}{\s56\qj \fi-170\li454\ri0\nowidctlpar\wrapdefault\faauto\rin0\lin454\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext56 \slink57 endnote text;}{\*\cs57 \additive \rtlch\fcs1 \af0\alang1024 \ltrch\fcs0 \fs24\lang1024\langfe1024\noproof \sbasedon10 \slink56 \slocked \ssemihidden Endnote Text Char;}{\*\cs58 \additive \rtlch\fcs1 \af0 \ltrch\fcs0 \super \sbasedon10 \ssemihidden footnote reference;}{\*\cs59 \additive \rtlch\fcs1 \af0 \ltrch\fcs0 \super \sbasedon10 endnote reference;}{\s60\ql \li0\ri0\sb60\sa60\keepn\nowidctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext60 acronym;}{\s61\qc \li0\ri0\sa120\nowidctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs20 \ltrch\fcs0 \b\fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext62 abstract title;}{\s62\qj \fi340\li1024\ri1024\widctlpar\wrapdefault\faauto\rin1024\lin1024\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 abstract;}{\s63\ql \li0\ri0\sb240\sa120\keepn\nowidctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs20 \ltrch\fcs0 \b\fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext0 contents_heading;}{\s64\ql \li425\ri0\sb240\sa60\keepn\nowidctlpar\tqr\tldot\tx8222\wrapdefault\faauto\rin0\lin425\itap0 \rtlch\fcs1 \ab\af0\afs20 \ltrch\fcs0 \b\fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext65 toc 1;}{\s65\ql \li512\ri0\sb60\sa60\keepn\nowidctlpar\tqr\tldot\tx8222\wrapdefault\faauto\rin0\lin512\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext66 toc 2;}{\s66\ql \li1024\ri0\sb60\sa60\keepn\nowidctlpar\tqr\tldot\tx8222\wrapdefault\faauto\rin0\lin1024\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext67 toc 3;}{\s67\ql \li1536\ri0\sb60\sa60\keepn\nowidctlpar\tqr\tldot\tx8222\wrapdefault\faauto\rin0\lin1536\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext68 toc 4;}{\s68\ql \li2048\ri0\sb60\sa60\keepn\nowidctlpar\tqr\tldot\tx8222\wrapdefault\faauto\rin0\lin2048\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext69 toc 5;}{\s69\ql \li2560\ri0\sb60\sa60\keepn\nowidctlpar\tqr\tldot\tx8222\wrapdefault\faauto\rin0\lin2560\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 \sbasedon0 \snext69 toc 6;}}{\*\rsidtbl \rsid3564724\rsid9849987\rsid15879383}{\mmathPr\mmathFont0\mbrkBin0\mbrkBinSub0\msmallFrac0\mdispDef0\mlMargin0\mrMargin0\mwrapRight0\mintLim0\mnaryLim0}{\info{\title Original file was paper.tex}{\doccomm Created using latex2rtf 2.3.3 r1230 (released Feb 26, 2013) on Wed Jul 31 12:12:02 2013}{\operator Samur Araujo}{\creatim\yr2013\mo7\dy31\hr12\min12}{\revtim\yr2013\mo7\dy31\hr12\min15}{\version3}{\edmins3}{\nofpages13}{\nofwords5690}{\nofchars32433}{\nofcharsws39830}{\vern33163}{\*\saveprevpict}}{\*\xmlnstbl {\xmlns1 http://schemas.microsoft.com/office/word/2003/wordml}}\paperw12280\paperh15900\margl2680\margr2700\margt2540\margb1760\gutter0\ltrsect \ftnbj\aenddoc\trackmoves0\trackformatting1\donotembedsysfont0\relyonvml0\donotembedlingdata1\grfdocevents0\validatexml0\showplaceholdtext0\ignoremixedcontent0\saveinvalidxml0\showxmlerrors0\aftnnar\horzdoc\dghspace120\dgvspace120\dghorigin1701\dgvorigin1984\dghshow0\dgvshow3\jcompress\viewkind1\viewscale160\rsidroot3564724 \fet0{\*\wgrffmtfilter 013f}\ilfomacatclnup0{\*\ftnsep \ltrpar \pard\plain \ltrpar\qj \li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \chftnsep \par }}{\*\ftnsepc \ltrpar \pard\plain \ltrpar\qj \li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \chftnsepc \par }}{\*\aftnsep \ltrpar \pard\plain \ltrpar\qj \li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \chftnsep \par }}{\*\aftnsepc \ltrpar \pard\plain \ltrpar\qj \li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \chftnsepc \par }}\ltrpar \sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\footerr \ltrpar \pard\plain \ltrpar\qc \li0\ri0\nowidctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \chpgn \par }}{\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang {\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang {\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang {\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang {\pntxta )}}{\*\pnseclvl5\pndec\pnstart1\pnindent720\pnhang {\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang {\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang {\pntxtb (}{\pntxta )}}{\*\pnseclvl8\pnlcltr\pnstart1\pnindent720\pnhang {\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang {\pntxtb (}{\pntxta )}}\pard\plain \ltrpar\qj \li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0\pararsid15879383 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 2 }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \par }\pard\plain \ltrpar\s61\qc \fi300\li0\ri0\sa120\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs20 \ltrch\fcs0 \b\fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Abstract\par }\pard\plain \ltrpar\qj \fi300\li1024\ri1024\widctlpar\wrapdefault\faauto\rin1024\lin1024\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  The task of transforming a string from one format into another is relevant for many information-processing tasks. Consider the task of transforming a list of names in the form }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 firstname lastname}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  (e.g. }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Michael Jackson}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ) to the form }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Last name First name}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  (e.g. }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Jackson Michael}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ). In many domains, identifying an appropriate set of operations that transforms one string to another is challenging, as the space of possible transformations is large. In this paper, we investigate the problem of learning string transformation rules from pairs of example strings. We propose a solid way to design these rules based on only four string operations: permutations, insertions, deletions and updates. Additionally, we propose an efficient algorithm to learn such rules, implemented as a combination of variations of well-known string manipulation algorithms. The proposed algorithm has the following desirable properties: it can express any string transformation; it can produce transformation rules that correctly transform a large part of the data, even when a limited number of training examples is provided; it is linear w.r.t the training sample size, which allows it to scale for large tasks; and it easy to understand and implement. We demonstrate the ability of our algorithm over real-world transformation tasks. The results indicate that the algorithm learns transformation rules that are generalizable for a broader range of strings to be transformed, using very few examples. The algorithm is especially useful on the area of data analysis where in preparation of the actual analysis data cleaning takes a considerable effort. \par }\pard\plain \ltrpar\s2\ql \li0\ri0\sb360\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel1\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 1  Introduction\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 The task of transforming a string from a source format into a target format is encountered in many information-processing tasks. Consider the task of transforming a list of names in the form }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 "firstname lastname"}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  (e.g. "Michael Jackson") into the target form }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 "lastname first letter of the firstname"}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  (e.g. "Jackson M"); or the task to transform a list of dates in the form "31/12/2009" into the form "12-31-2009". These types of string transformations are performed by hundreds of millions of end-users of spreadsheets and data cleaning tools every day. Currently, the number of people transforming data is so large that Microsoft has recently implemented a string transformation functionality [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_conf_popl_Gulwani11 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 2}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] in the Excel Spreadsheet 2013 [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_journals_cacm_GulwaniHS12 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 3}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] and Google has lunched Google Refine}{\rtlch\fcs1 \af0 \ltrch\fcs0 \cs58\super\insrsid15879383\charrsid9849987 \chftn {\footnote \ltrpar \pard\plain \ltrpar\s54\ql \fi-113\li397\ri0\widctlpar\wrapdefault\faauto\rin0\lin397\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \cs58\super\insrsid15879383\charrsid9849987 \chftn }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  http://code.google.com/p/google-refine/}}}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , both aiming to support end-users (specially non-programmers) on data transformation related tasks. Gulwani el. al [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_journals_cacm_GulwaniHS12 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 3}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] introduce an effective way to do string transformations. They allow end-users to provide an example of a transformation that they want to obtain, and their tools can generalize the transformation to the rest of their data. This }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Programming by Example strategy}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  (PBE) [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_journals_aim_Lau09 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 4}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] allows non-programmers (e.g. data analysts, business analysts) to perform transformations that before only expert programmers could perform using shell scripts combined with Awk}{\rtlch\fcs1 \af0 \ltrch\fcs0 \cs58\super\insrsid15879383\charrsid9849987 \chftn {\footnote \ltrpar \pard\plain \ltrpar\s54\ql \fi-113\li397\ri0\widctlpar\wrapdefault\faauto\rin0\lin397\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \cs58\super\insrsid15879383\charrsid9849987 \chftn }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  https://en.wikipedia.org/wiki/AWK}}}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , regular expressions or other advanced programming techniques. \par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Although PBE tools are undoubtedly useful for non-programmers that need to perform string transformation to achieve their data analysis, to design these tools is a challenging task. Particularly, it becomes challenging because users want to provide as few transformation examples as possible, and to produce rules from this limited set of examples that generalize for the rest of the data is not obvious. \par To tackle this problem, existing methods either focus on a small set of string transformations or require a large amount of examples to guarantee accurate transformations. For instance, in the well-known area of record matching, some authors [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_journals_pvldb_ArasuCK09 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 1}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] have proposed to use string transformations in the process of matching of records. Basically, these methods concern the problem of learning one-to-one mapping rules from pairs of matching examples, i.e., they learn tokens that map to each other. Then they can use these mappings to improve the matching of records. Because they do not learn the character replacements that lead a string into another, these learned transformation rules can only transform what they have observed in the set of examples, i.e., the learned rules generalize poorly. For instance, they can learn }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 North}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 N}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , but they cannot transform "South" into "S". \par Other authors [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_conf_icai_MichelsonK09 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 6}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ], looked into the problem of finding mappings between synonyms, abbreviations and acronyms, which are types of transformations that cannot be generalized for other strings. For example, a rule that transforms }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 New}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 York}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Big}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Apple}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  is specific for the string "New York" and cannot be applied in any other string. This problem (that can also be described as learning a dictionary) is considered orthogonal to the problem of learning string transformation rules of interest here. \par Closely related to our problem is the work of Okazaki et al. [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_conf_emnlp_OkazakiTAT08 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 8}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ]. They tackle the problem of word lemmatization (e.g. }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 studying}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 study}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ) and spelling correction (e.g. }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 vapour}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 vapor}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ) by learning transformations to be applied on the strings. Their work limits the transformations to a single substring replacement in the source string. Although quite effective for the transformation task that they designed, their method requires a large number of examples to learn the transformation rules. Apart from the works mentioned so far, only few works exist tackling the same problem. We discuss them in more detail, in Sec. }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMsec_relatedwork \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 6}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 .\par This paper presents at general string transformation algorithm that learns transformation rules from a few given examples. It is standalone approach that can be integrated into any data processing tool to support the high demand for non-programmers for data processing. \par Given a pair of strings (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ), this work tackles the problem of learning a }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 transformation rule}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  (for short, }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 a rule}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ), which transforms }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  into }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , so that this learned rule can be used to transform an unseen string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 s}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  into }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 t}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , where }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 s}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  is in the same form as }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . For example, a rule learned from the pair of strings ("31/12/2009", "12-31-2009") should also transform "01/04/2012" into "04-01-2012" . Particularly, a transformation rule is considered as a set of characters permutations, insertions, deletions and updates that takes place in }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  to transform it into }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . We will use the notation }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  to denote a transformation of a string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  into }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  (e.g. }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Michael}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Jackson}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Michael}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 J}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 .). \par Table }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMtable_ruleexamples \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 1}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  shows a few relevant examples of transformations addressed in this paper. They are real-world use cases drawn from data cleaning and spreadsheet processing literature, representing user questions in data cleaning forums and discussion lists. \par }\pard\plain \ltrpar\s41\qc \li0\ri0\sb240\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \par }\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs10\insrsid15879383 Table {\*\bkmkstart BMtable_ruleexamples}1{\*\bkmkend BMtable_ruleexamples}: Transformation Examples}{\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs10 \ltrch\fcs0 \v\fs10\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\tc {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs10\insrsid15879383 1 Transformation Examples\tcf116}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs10\insrsid15879383 \par \par   \par }\pard\plain \ltrpar\qj \fi300\li0\ri0\sb240\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 The method proposed in this paper differs from the state-of-the-art string transformation methods in two ways. First, it learns an edit-distance based transformation rule (i.e. a set of characters permutations, insertions, deletions and updates) from a single example (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ), which is the most general set of basic operations that can transform }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . The learned rule not just can transform }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  but also an unseen string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 s}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  similar to }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  into its desired target form }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 t}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . Second, it focuses on string transformations that change the formatting of a string into another. For example, in Table }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMtable_ruleexamples \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 1}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , a rule that transforms }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )\u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  must also transforms }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 s}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )\u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 t}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 .\par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 The proposed method requires only a few positive examples to learn transformation rules, which are user-provided examples of valid transformations }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . The basic idea is to learn a rule for each example transformation that the user has to perform. Then, all learned rules are used to transform the remaining strings that the user has at hand. In practice, we learned a series of rules from the example set, and pick the rule to apply based on features derived from the string to be transformed. Obviously, we assume that the user can provide a compilation of examples. We do so, because usually the user has a specific need, over a specific dataset and examples are not available beforehand and cannot be generated or selected by any automatic mean. The user can potentially participate in the process providing more examples when she observes incorrect transformations being produced. This is the way to increase the quality of the examples and it is widely accepted as a reasonable approach to the problem. In this work, we assume that the examples are given, and we focus on learning the transformation rules.\par }\pard\plain \ltrpar\s3\ql \li0\ri0\sb120\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel2\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 1.1  Overview and Contributions\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Basically, a string can be transformed into another, by eliminating the differences between them, i.e., parts of a string that are not in another and vice-versa. To do so, the basic edit-distance operations of characters permutations, insertions, deletions and updates can be applied. Although to find a set of operations (a transformation rule) that generates a transformation }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  can be trivial (e.g. delete all characters in }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  and add all characters of }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ); to find a set of operations that transforms a large number of string correctly is however a challenge. The problem involves not just selecting the best set of operations to compose a rule but also how to express these operations as general as possible. To this end, we propose a set of primitive string operations that can precisely describe a transformation }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  but can also be used to correctly transform a large number of unseen strings similar to }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . To make the problem linear w.r.t the size of the learning sample, each rule is learned independently for each pair of example strings (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ). As this learning approach leads to many learned rules, a method is proposed to select, automatically, the likely probable rule to transform correctly an unseen string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 s}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 .\par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 The problem of learning a general transformation rule is formalized in the Section }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMsec_problem \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 2}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . Any transformation can be expressed with four basic string operations. We propose a generalization of the four basic string operations, so that a transformation rule learned from a single example can transform other strings with similar features. As these operations include characters permutation as well, in Section }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMsec_algorithm \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 3}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  we provide a linear time algorithm to find the best permutation of characters of }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  for permutation-based transformations (e.g. 01/04/2012\u8594\'5f04/01/2012). In Section 4, we describe an algorithm to select a learned rule to transform a given unseen string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 s}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . We demonstrate empirically that in practice, using a few examples, the algorithm produces transformation rules that generalize for a large number of strings.\par We conduct a detailed empirical investigation of our algorithm (Section 5) using real-world string transformation scenarios. For example, in one of these scenarios the user faces the task of putting book titles in a standard format, given a dataset of available titles described in a non-standard format, i.e., transformation like  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Art}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 of}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Science}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 The}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 The}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Art}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 of}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Science}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . We study various aspects of the algorithm including the generality of learned rules and the linearity w.r.t. the input size. Particularly, we investigate the accuracy of the algorithm in the real-world setting where a very limited set of examples is provided. We do so because in the real world transformation tasks, the user wants to obtain the correct string transformations providing the minimal number of examples as possible. Also, we compare the proposed algorithm, namely }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 STransformer}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , to the state-of-the-art string transformation algorithm implemented in Microsoft Excel 2013, namely }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 FlashFill}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . The results show that STransformer is 30% more accurate, in average. Additionally, its accuracy is less dependent from the examples than FlashFill, which is an important property of the STransformer given that variety of examples is large. Finally, we discuss related work in Section 6 and conclude the paper in Section 7.\par }\pard\plain \ltrpar\s2\ql \li0\ri0\sb240\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel1\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 {\*\bkmkstart BMsec_problem}2{\*\bkmkend BMsec_problem}  Learning Transformations\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 This section formulates our problem. The input for the transformation-learning problem is a set of N positive string transformation examples }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ \u923\'5f\\s\\up5(}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 +}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )=\{(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )\\,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )):}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 i}{\rtlch\fcs1 \af3 \ltrch\fcs0 \f3\insrsid15879383 \u8712\'08}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 [1\\,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 N}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ]\}}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , where }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )\\,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ))}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  are pairs of strings from an arbitrary domain, for example, organizations names or log file entries. Our high-level goal is to learn transformations from these examples that can be applied to new instances of our problem where the desired output is not yet available. First we introduce basic definitions, and then we formulate the learning problem.\par }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid9849987  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \par }\pard\plain \ltrpar\s3\ql \li0\ri0\sb120\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel2\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 3.1  Rule Learning\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 The rule learner algorithm is composed of four parts, corresponding to the four basic string operations permutation, insertion, deletion and update. Intuitively, the algorithm learns possible permutations in }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , then on the permuted string }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 p}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  it identifies insertions and deletions to transform it to }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 _}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 d}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , such that }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ |}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 _}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 d}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )|=|}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 |}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ; and finally, in the resultant string }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 _}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 d}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , it learns the character replacements necessary to transform }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 _}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 d}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  into }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 .\par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0\pararsid9849987 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Firstly, we describe the algorithm to find a relative position in }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , to be used in the string operations. }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid9849987  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \par }\pard\plain \ltrpar\s3\ql \li0\ri0\sb120\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel2\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 3.6  Discussion\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Table }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMtable_ruleexamples \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 1}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  shows a large variety of examples of string transformations: }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )\u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  and }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 s}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )\u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 t}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . The algorithm just described can learn a rule using as example a transformation rule }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ \u936\'5f\\s\\up(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 G}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 ,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 \\s\\do4(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs13\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 )\\,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 \\s\\do4(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs13\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 )}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  and produce a correct transformation for any string }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 s}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  in this table (i.e.}{\rtlch\fcs1 \af0 \ltrch\fcs0 \charscalex50\insrsid15879383 \~}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 s}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )\u8594\'5f\\s\\up5(}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 \u936\'5f\\s\\up(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs13\insrsid15879383 G}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs13\insrsid15879383 ,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs13\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs13\insrsid15879383 \\s\\do3(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs10\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs13\insrsid15879383 )\\,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs13\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs13\insrsid15879383 \\s\\do3(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs10\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs13\insrsid15879383 )}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 )}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 t}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ). Although, some of these transformations can be easily expressed by programmers, non-programmers do not have the skills to express it. The proposed method allows them to perform a large range of non-trivial transformations by simply providing examples.\par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 As a design decision, the rules are learned and applied independently of each other. This avoids the exponential problem of searching for the combination of operations that maximize the coverage over all examples. Obviously, it is impossible to learn a rule with maximal }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Cov}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (\u936\'5f\\s\\up(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 G}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 ,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 \\,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )\\,\u923\'5f\\s\\up5(}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 +}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ))}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  for any arbitrary string pair (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ) and }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ \u923\'5f\\s\\up5(}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 +}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , considering only information in (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ). However, in Sec. }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMsec_evaluations \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 5}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , we will show that the rule learner algorithm produces high coverage rules over real-world transformation tasks, which can be properly selected to transform an unseen string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 s}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , correctly. \par }\pard\plain \ltrpar\s2\ql \li0\ri0\sb240\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel1\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 {\*\bkmkstart BMsec_rulelearner}4{\*\bkmkend BMsec_rulelearner}  Rule Selector Method\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 In this section, we describe our method to tackle the second learning problem. \par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Given a transformation model }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ \u937\'bd(\u923\'5f\\s\\up5(}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 +}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ))}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  and a pair of strings (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 x}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 y}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ), we model the problem of finding a transformation rule }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ \u936\'5f\\s\\up(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 G}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 ,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 \\,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}{\rtlch\fcs1 \af3 \ltrch\fcs0 \f3\insrsid15879383 \u8712\'08}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u937\'bd(\u923\'5f\\s\\up5(}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 +}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ))}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , such that }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Validity}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (\u968\'5f\\s\\up(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 G}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 ,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 \\,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )\\,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 x}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 y}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )=1}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , as a classification problem. Our training data are pairs of string }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )\\,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\do5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ))}{\rtlch\fcs1 \af3 \ltrch\fcs0 \f3\insrsid15879383 \u8712\'08}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u923\'5f\\s\\up5(}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 +}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  (observations) and rules in }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ \u968\'5f\\s\\up(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 G}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 ,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 \\s\\do4(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs13\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 )\\,}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 \\s\\do4(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs13\insrsid15879383 i}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 )}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}{\rtlch\fcs1 \af3 \ltrch\fcs0 \f3\insrsid15879383 \u8712\'08}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u937\'bd(\u923\'5f\\s\\up5(}{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs16\insrsid15879383 +}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ))}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  (categories). Then given a new string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 x}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , the task is to assign a specific rule (category) to it, based on the features extracted from }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 x}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . We use a }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Naive Bayes Classifier}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  as classifier. \par During the training phase, where }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  and }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  are available, the set of trigrams (3-grams) of the strings }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\up5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 c}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  and }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\up5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 c}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , and the frequency of the trigrams of }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\up5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 c}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  were used as features. Precisely, the set of features can be represented as: }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Trigram}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )\u8722\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Trigram}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ))}{\rtlch\fcs1 \af129 \ltrch\fcs0 \f129\insrsid15879383 \u8746\'5f}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Trigram}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\up5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 c}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ))\u8722\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Trigram}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\up5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 c}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )))}{\rtlch\fcs1 \af129 \ltrch\fcs0 \f129\insrsid15879383 \u8746\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 freq}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Trigram}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\up5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 c}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )))}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 .\par A frequency was represented by concatenating the trigram with its frequency value, e.g., for a trigram }{\rtlch\fcs1 \ab\af0 \ltrch\fcs0 \b\insrsid15879383 ull}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  with }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 f}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (}{\rtlch\fcs1 \ab\af0 \ltrch\fcs0 \b\insrsid15879383 ull}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )=2, the feature was represented as }{\rtlch\fcs1 \ab\af0 \ltrch\fcs0 \b\insrsid15879383 ull2}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 .\par During the classification phase, where only the string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 x}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  to be transformed is available, the set of trigrams of the string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 x}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  and }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 x}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\up5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 c}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , and the frequency of the trigrams of }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 x}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\up5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 c}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  were used as features. Precisely, this set of features can be represented as: }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Trigram}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 x}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}{\rtlch\fcs1 \af129 \ltrch\fcs0 \f129\insrsid15879383 \u8746\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Trigram}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 x}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\up5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 c}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ))}{\rtlch\fcs1 \af129 \ltrch\fcs0 \f129\insrsid15879383 \u8746\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 freq}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Trigram}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 (}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 x}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\up5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 c}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )))}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 .\par Notice that the difference of the set of trigrams used above gives exactly the trigrams that change during a transformation }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 v}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . During the classification phase, if a string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 x}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  shares these features (trigrams) that represent a rule }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 m}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , it is likely that }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 m}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  is the best candidate rule to transform }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 x}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  correctly. We observed that this set of features produces satisfactory results; further extension of this method could engineer better features even further, e.g., using the techniques of [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_1183917 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 7}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ].\par As any other classification task, we assume the user can collect a representative and discriminative training sample to obtain a satisfactory performance of this method. We acknowledge that for specific transformation tasks other machine learning approaches may perform better. However, in Sec. }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMsec_evaluations \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 5}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , we will show that the effectiveness of the Naive Bayes Classifier is sufficient for our purpose, in average. \par }\pard\plain \ltrpar\s2\ql \li0\ri0\sb240\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel1\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 {\*\bkmkstart BMsec_evaluations}5{\*\bkmkend BMsec_evaluations}  Evaluation\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 In this section, we investigate empirically three aspects of our method: the coverage of the rules produced by the rule learner, the accuracy of the rule selector, and the learning time of the rule learner. In the end of this section, we compare our algorithm, namely }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 STransformer}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , to a state-of-the-art string transformation method. \par }\pard\plain \ltrpar\s3\ql \li0\ri0\sb120\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel2\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 5.1  Data\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 In this investigation, four datasets were constructed based on real-world string transformation tasks drawn from data cleaning and spreadsheet processing literature. As we will discuss, these four scenarios show the power of STransformer, which can solve different transformation tasks, requiring a very limited set of examples. \par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \ab\af0 \ltrch\fcs0 \b\insrsid15879383 Abbreviations Dataset.}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  The first dataset is a collection of 2034 organizations names and their abbreviations, where we study a real-case scenario of string transformation. In this }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 abbreviations}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  dataset, the overall task was to learn transformation rules from a few examples that could generate the abbreviations to the full organizations names, e.g. }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Youth}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Hostels}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Association}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 YHA}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 University}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 of}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 New}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Hampshire}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 UNH}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . Then, the learned rules were used to transform all organizations names into their abbreviations.\par }{\rtlch\fcs1 \ab\af0 \ltrch\fcs0 \b\insrsid15879383 Books Dataset.}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  The second dataset is a collection of book titles from the }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Book Crossing dataset }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_Ziegler_2005_IRL_1060745_1060754 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 15}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ], where we study a data cleaning scenario. We obtained 51690 titles from books records where the titles start with an article (e.g. "The", "La", "El", "An"). Then, we shifted the article to the end of the sentence, after inserting a comma and a space, as shown in this example: "Cloud, The" instead of "The Cloud". Consequently, the task was to put the title in the original form, i.e., to shift the article to the beginning of the sentence and to remove the additional comma and space. As in the previous scenario, rules were learned from a limited given set of examples, and then used to transform all titles in the correct conventional form, i.e. }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Cloud}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 The}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 The}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Cloud}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . \par }{\rtlch\fcs1 \ab\af0 \ltrch\fcs0 \b\insrsid15879383 Songs Dataset.}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  The third dataset was build to reflect a usage scenario of smart copy-paste. We selected all songs of the band REM from Wikipedia pages, in total 184 songs. An example of a song extracted from the Wikipedia page is: }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 "Shiny Happy People" - 3:44}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . In this }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 song}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  dataset, the task was to learn rules that could extract the song titles from the copied text, i.e. "Shiny Happy People" \- 3:44 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Shiny}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Happy}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 People}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . \par }{\rtlch\fcs1 \ab\af0 \ltrch\fcs0 \b\insrsid15879383 Dates Dataset.}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  The last dataset represents another data cleaning case; we used an artificial dataset containing 366 dates in format }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 "month day, year"}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , where }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 month}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  is represented by its abbreviated name (e.g. }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Jan}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  02, 2013). The task was to learn rules that could transform these dates to the format }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 "day/month/year"}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , where the }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 month}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  is represented by its decimal representation (e.g. 02/01/13), i.e.,  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Jan}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  02, 2013\u8594\'5f02/01/13. This dataset is quite homogeneous requiring exactly 12 rules to transform all strings, which map to the twelve-month names and their equivalent decimal representations. Contrarily, all other datasets evaluated are heterogeneous, i.e., there is no logical pattern or obvious regularity that can explain their data beforehand. Particularly, we selected this Dates dataset to show that when there is regularity in the data, the algorithm can learn it with 100% accuracy. \par We manually constructed the ground truth for all strings in all datasets. To ensure reproducibility of our results both datasets and the implementation of the proposed algorithm are available for download}{\rtlch\fcs1 \af0 \ltrch\fcs0 \cs58\super\insrsid15879383\charrsid9849987 \chftn {\footnote \ltrpar \pard\plain \ltrpar\s54\ql \fi-113\li397\ri0\widctlpar\wrapdefault\faauto\rin0\lin397\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \cs58\super\insrsid15879383\charrsid9849987 \chftn }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  https://github.com/samuraraujo/StringTransformation}}}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . \par }\pard\plain \ltrpar\s3\ql \li0\ri0\sb120\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel2\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 5.2  Evaluation Metric \par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 To assess the quality of the rule learner algorithm (i.e. the rule coverage), the }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 maximal coverage}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  was used, which is the minimal number of example transformations that have to be learned to correctly transform all strings. We evaluated the rule learner with three different configurations of n-grams, in relative position algorithm (Alg. }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMalg_relativeposition \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 1}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ): N1 (1-gram), N2 (2-grams) and N3 (3-grams).\par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 To assess the quality of the rule selector algorithm, the }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 accuracy measure}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  was used. It is defined below:\par }\pard\plain \ltrpar\s25\ql \li0\ri0\sb120\sa120\keep\widctlpar\tqc\tx3450\tqr\tx6900\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \tab }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \tab (7)\par }\pard\plain \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Where }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 #correct transformations}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  stand for the number of transformations that the rule selector produces correctly. And }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 #string pairs in the ground truth}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  stands for the number of strings in the ground truth, i.e. the total number of strings that have to be transformed.\par }\pard\plain \ltrpar\s3\ql \li0\ri0\sb120\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel2\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 5.3  Rule Coverage\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Table }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMtable_rulecoverage \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 2}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  shows the maximum coverage per task. It indicates that indeed the rule learner algorithm needs a relatively small number of examples to correctly transform all strings in the ground truth, in average. Specially, in the Books, Songs and Dates datasets, N2 requires 157, 2 and 12 examples; respectively. This equates to 0.29%, 1% and 3% of the data; respectively. \par }\pard\plain \ltrpar\s41\qc \li0\ri0\sb240\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383  \par }\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 Table {\*\bkmkstart BMtable_rulecoverage}2{\*\bkmkend BMtable_rulecoverage}:  Maximal Coverage Per Task }{\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs18 \ltrch\fcs0 \v\fs18\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\tc {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 2  Maximal Coverage Per Task \tcf116}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 \par \par   \par }\pard\plain \ltrpar\qj \fi300\li0\ri0\sb240\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 In total, 305 (for N2) examples are necessary to obtain maximal coverage in the Abbreviations dataset. This equates to 15% of the data. Although this is a relative large number of examples in our context, as observed in Table }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMtable_coverageabbreviations \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 3}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , a small set of rules (precisely, 7 rules) covers 78% of the examples (i.e., 1577 out of 2034 examples). It indicates that seven rules can transform 78% of the data, correctly. This is quite satisfactory coverage considering that there are precisely 244 cases (12% of the data) that can only be transformed by completely distinct rules, i.e., no general rule could transform them. Examples of these cases are: }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Zeta}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Psi}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 ZPsi}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Nuns}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 of}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 the}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Order}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 of}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 St}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Clare}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 OSC}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  and }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Congregation}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 of}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 the}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Holy}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Ghost}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 CSSp}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . Consequently, to achieve 100% coverage with seven or less rules is not truly possible in this data due to the lack of regularity in the data. In practice, no method can learn rules from other available examples that transform these 244 cases correctly. Although, this is a very heterogeneous dataset with distinct forms of abbreviating the organizations names, for the cases where there are regularity, the algorithm learns them with acceptable coverage. Notice that if we exclude these 244 cases, the coverage would be 88%.\par }\pard\plain \ltrpar\s41\qc \li0\ri0\sb240\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383  \par }\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 Table {\*\bkmkstart BMtable_coverageabbreviations}3{\*\bkmkend BMtable_coverageabbreviations}:  The first 7 rules with the highest coverage for the Abbreviations dataset using N2. }{\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs18 \ltrch\fcs0 \v\fs18\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\tc {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 3  The first 7 rules with the highest coverage for the Abbreviations dataset using N2. \tcf116}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 \par \par   \par }\pard\plain \ltrpar\qj \fi300\li0\ri0\sb240\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Similarly to the Abbreviations dataset, in the Books dataset, many examples, in total 157 (for N2), are necessary to obtain maximal coverage. However, as observed in Table }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMtable_coveragebooks \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 4}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , a very small set of rules (precisely, 11 rules) covers a large number of the examples (i.e., 51282 examples or 99% of the data). It confirms that the algorithm is effective in learning transformation rules from a few examples, when the regularity is presented in the data. As indicated in this case, with 11 examples, it covers 99% of the data, which is a quite high coverage. \par }\pard\plain \ltrpar\s41\qc \li0\ri0\sb240\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383  \par }\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 Table {\*\bkmkstart BMtable_coveragebooks}4{\*\bkmkend BMtable_coveragebooks}:  The first 11 rules with the highest coverage for the Books dataset using N2. }{\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs18 \ltrch\fcs0 \v\fs18\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\tc {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 4  The first 11 rules with the highest coverage for the Books dataset using N2. \tcf116}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 \par \par   \par }\pard\plain \ltrpar\qj \fi300\li0\ri0\sb240\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 In the case of the Songs dataset, the algorithm (with N2) needs only 2 examples. This shows that it can capture the regularity in the data quite precisely. \par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 In all configurations (N1, N2 and N3), it performed optimally for Dates dataset, requiring exactly 12 examples, to capture the 12 distinct patterns of dates in the ground truth, i.e., the twelve-month names and their equivalent decimal representations. \par Concluding, we recommend using N2 instead of N1, because N2 is more discriminative than N1, even though slightly more examples were necessary in the Books case.\par }\pard\plain \ltrpar\s3\ql \li0\ri0\sb120\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel2\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 5.4  Rule Selector Accuracy\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 To verify the rule selector accuracy, examples with maximal coverage were selected for each task; except for the Abbreviations and Books tasks, where only 7 examples with 78% coverage and 11 examples with 99% coverage were selected, respectively. As these examples produce rules that accumulate 100% coverage (78% for the Abbreviations examples and 99% for the Books examples), we generated rules using the selected examples, and then we verified the accuracy of the rule selector in selecting a rule that transforms correctly a new string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 s}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . Table }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMtable_abbreviationsexamples \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 5}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMtable_bookexamples \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 6}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMtable_songexamples \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 7}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  and }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMtable_datesexamples \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 8}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  show the examples used to build the rules for the Abbreviations, Books, Songs, and Dates transformation tasks; respectively. \par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 These examples were manually selected, by drawing from the set of examples a few exemplars with evident difference in their features (precisely, strings with different }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  EQ }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 u}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \\s\\up5(}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\fs16\insrsid15879383 c}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 )}}{\fldrslt }}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  trigrams). Given that the majority of the example strings are quite similar, applying a random selection of examples does not make sense in this setting, because likely we would select examples that produce the same rule; consequently, resulting in low coverage and accuracy. To such an approach to be effective, we would have to consider a large number of examples, which goes against our goal here.\par }\pard\plain \ltrpar\s41\qc \li0\ri0\sb240\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs14\insrsid15879383  \par }\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs14\insrsid15879383 Table {\*\bkmkstart BMtable_abbreviationsexamples}5{\*\bkmkend BMtable_abbreviationsexamples}: Abbreviations Examples}{\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs14 \ltrch\fcs0 \v\fs14\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\tc {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs14\insrsid15879383 5 Abbreviations Examples\tcf116}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs14\insrsid15879383 \par \par   \par }\pard\plain \ltrpar\s41\qc \li0\ri0\sb480\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383  \par }\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 Table {\*\bkmkstart BMtable_bookexamples}6{\*\bkmkend BMtable_bookexamples}: Book Titles Examples}{\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs18 \ltrch\fcs0 \v\fs18\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\tc {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 6 Book Titles Examples\tcf116}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 \par \par   \par }\pard\plain \ltrpar\s41\qc \li0\ri0\sb480\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383  \par }\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 Table {\*\bkmkstart BMtable_songexamples}7{\*\bkmkend BMtable_songexamples}: Song Examples}{\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs18 \ltrch\fcs0 \v\fs18\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\tc {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 7 Song Examples\tcf116}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 \par \par   \par }\pard\plain \ltrpar\s41\qc \li0\ri0\sb480\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383  \par }\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 Table {\*\bkmkstart BMtable_datesexamples}8{\*\bkmkend BMtable_datesexamples}: Dates Examples}{\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs18 \ltrch\fcs0 \v\fs18\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\tc {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 8 Dates Examples\tcf116}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 \par \par   \par }\pard\plain \ltrpar\qj \fi300\li0\ri0\sb240\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Table }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMtable_results \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 9}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  shows the accuracy of rule selector for each transformation task using the examples previously described. For the Abbreviations, Books, Songs and Dates task, the accuracy was 74%, 83%, 96%, 100%; respectively. Although, the naive classifier is very sensitive w.r.t the quantity and quality of the examples, particularly when a few examples are provided, it performed satisfactorily with high accuracy on average. This is due to the quality of the examples provided, which were manually selected in this investigation. Particularly, in the Books task, the accuracy was a bit lower (83%) than expected. Given that selected Books examples have high coverage, features that were insufficiently discriminative can explain this accuracy. The Abbreviations task had the lowest accuracy (74%); however, the coverage of the examples was only 78%, for this task. It means that its relative accuracy, w.r.t its coverage, was 95%. \par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Overall, we observed that the rule learner indeed learned rule that were quite general, the most of the incorrect transformations observed were due to the rule selector that selected incorrect rules. Concluding, the results demonstrate the feasibility of STransformer for general string transformations tasks. Basically, users without programming knowledge can produce useful string transformations by simply supplying a set of examples. Future extensions could engineer better features to improve the effectiveness of rule selector even further, e.g., using the techniques of [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_1183917 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 7}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ].\par }\pard\plain \ltrpar\s41\qc \li0\ri0\sb240\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383  \par }\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 Table {\*\bkmkstart BMtable_results}9{\*\bkmkend BMtable_results}: Accuracy of the Rule Algorithm With N2}{\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs18 \ltrch\fcs0 \v\fs18\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\tc {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 9 Accuracy of the Rule Algorithm With N2\tcf116}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 \par \par   \par }\pard\plain \ltrpar\s3\ql \li0\ri0\sb360\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel2\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 5.5  Runtime Cost\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Now, we show the linearity of the rule learner algorithm. For this evaluation, we used an Intel Core 2 Duo, 2.4 GHz, 4 GB RAM, using a FUJITSU MHZ2250BH FFS G1 248 GB hard disk. As noted in Sec. 3, the algorithm is linear which allows it to scale well with the number of examples, considering transformation tasks where a large number of examples is available and necessary. We empirically study the performance of the learner algorithm with an increasing number of input examples. We use subsets of increasing cardinality drawn from the Books dataset. Fig. }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMfig_time \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 3}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  shows the running time of four runs for various sample sizes. We observe a linear increase in running times as the number of input examples grows, as expected from our analysis in Sec. 3.\par }\pard\plain \ltrpar\s40\qc \fi300\li0\ri0\sb240\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  \par }\pard\plain \ltrpar\s23\qc \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid9849987  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  \par }\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Figure {\*\bkmkstart BMfig_time}3{\*\bkmkend BMfig_time}: Learning time varying the sample size for the Books dataset. We considered 4 runs for each sample size.}{\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \v\fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\tc {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 3 Learning time varying the sample size for the Books dataset. We considered 4 runs for each sample size.\tcf102}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \par }\pard\plain \ltrpar\s3\ql \li0\ri0\sb360\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel2\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 5.6  Performance Comparison\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Finally, we compare the STransformer to the state-of-the-art string transformation proposed in [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_conf_popl_Gulwani11 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 2}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_journals_cacm_GulwaniHS12 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 3}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] (namely, }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 FlashFill}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ). Their algorithm is implemented in the Microsoft Excel 2013, available as a command in the Excel\rquote s toolbar. Particularly, we used Excel 2013 version 15.0.4505.1001 in this evaluation. \par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 We measured the accuracy of both systems in solving 4 tasks: Abbreviations, Books, Songs and Dates, which use the same datasets described in the previous evaluations. For each task, we randomly selected a single example from a list of examples that have regular features (e.g., common trigrams) in the data, so that this transformation example had a clear pattern that could be learned. In both systems, a rule was learned from the selected example, and then used to transform the rest of the data.\par Particularly, for STransformer, a single rule was learned from this single example and used to transform the rest of the data. In the FlashFill, this single example was input into Excel interface as the example of the desired transformation. Then, we apply the FlashFill Excel command in the rest of the data. Finally, we measured the accuracy of each system for each task. We repeated this process five times for different examples and computed the average accuracy. Table }{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BMtable_comparisonflashfill \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 10}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  shows the results. \par }\pard\plain \ltrpar\s41\qc \li0\ri0\sb240\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383  \par }\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs24 \ltrch\fcs0 \fs24\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 Table {\*\bkmkstart BMtable_comparisonflashfill}10{\*\bkmkend BMtable_comparisonflashfill}: Average accuracy per systems.}{\pard\plain \ltrpar\s39\ql \li0\ri0\sb120\sa120\keep\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs18 \ltrch\fcs0 \v\fs18\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\tc {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 10 Average accuracy per systems.\tcf116}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \fs18\insrsid15879383 \par \par   \par }\pard\plain \ltrpar\qj \fi300\li0\ri0\sb240\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 Considering the average accuracy among all tasks, STransformer\rquote s accuracy was superior to FlashFill\rquote s accuracy. Particularly, STransformer\rquote s average accuracy per task was superior in the Books (72%), Songs (92%) and Dates (8%) tasks, compared to FlashFill\rquote s average accuracy in the Books (46%), Songs (55%) and Dates (1%) tasks. FlashFill\rquote s average accuracy in the Abbreviations task was 60% while STransformer\rquote s average accuracy in this task was 39%. The results indicates that in some individual runs FlashFill had a better performance than STransformer (e.g. FlashFill - 3, in Abbreviations and Books tasks.); however, STransformer\rquote s accuracy was stable, i.e., it did not vary for different examples (different runs), contrarily to FlashFill\rquote s accuracy that varied a lot in all tasks for different examples. \par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 These results indicate that STransformer produces more general rules than FlashFill, in average. Also, the results expose a strong characteristic of STransformer: it is robust, i.e., its accuracy is less impacted by different examples than FlashFill. This is a desirable property, given that the universe of examples available is diverse in these types of tasks. \par In this evaluation, some tasks reported low accuracy (e.g. Dates) because a single rule could not cover 100% of the universe of transformations; however, the results clearly reflects the ability of each system in producing general rules from a single example. Comparatively, in practice, from a single example, STransformer can transform a larger portion of the data correctly than FlashFill. \par Concluding, the edit-distance based transformation rules generalize much better in real data than the grammar-based string transformation approach proposed by FlashFill. STransformer has less than 2000 lines of code and can be easily be integrated to PBE interfaces, such as Microsoft Excel 2013. \par }\pard\plain \ltrpar\s2\ql \li0\ri0\sb240\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel1\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 {\*\bkmkstart BMsec_relatedwork}6{\*\bkmkend BMsec_relatedwork}  Related Work\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 In this section, we discuss the related work and other methods addressing string transformations.\par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \ab\af0 \ltrch\fcs0 \b\insrsid15879383 Learning Association Rules}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . Arasu et al. [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_journals_pvldb_ArasuCK09 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 1}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] studied the problem of learning a set of transformation rules given a set of examples matches. In their problem, they assume that a transformation rule maps a sequence of tokens to another sequence of tokens (e.g. 1}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 st}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Ave}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 First}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 Avenue}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ). These mappings or associations are then used to transform a string into another. A limitation of their approach is that rules cannot be applied over unseen tokens. For instance, the rule }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 North}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \u8594\'5f}{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 N}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 , cannot be used to transform "South" into "S". Moreover, their algorithm needs a large number of examples to generate useful rules. Michelson et al. [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_conf_icai_MichelsonK09 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 6}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] studied the problem of heterogeneous transformations, which are translations between strings that are not characterized by a single function. E.g. abbreviation, synonyms and acronyms. Addressing the problem of record linkage, Patro et al. [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_conf_dexa_PatroW11 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 9}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] proposed an automatic method to extract top-k high quality transformation rules given a set of possibly co-referent record pairs. Tejada et al. [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_conf_kdd_TejadaKM02 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 13}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] addressed a similar problem. Although relevant, these transformations are complementary to the class of transformations that we looked at in our work. We looked into transformations that change the formatting of a string, instead of a mapping based transformations.\par }{\rtlch\fcs1 \ab\af0 \ltrch\fcs0 \b\insrsid15879383 Learning Candidate Transformations}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . Okazaki et al. [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_conf_emnlp_OkazakiTAT08 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 8}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] studied the problem of generating candidate strings to which a given string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 s}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  is likely to be transformed. They propose a supervised approach that uses sub-string substitution rules as features and score them using an L1 regularized logistic regression model. Then their model selects the best target string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 t}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  based on the probability of a string }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 t}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383  be a transformation to }{\rtlch\fcs1 \ai\af0 \ltrch\fcs0 \i\insrsid15879383 s}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . As they use a discriminative model, they required a large number of both positive and negative examples. Moreover, the authors state that their model cannot handle changes at phrase/term level, e.g., "Michael Jackson" and "Jackson Michael", which we propose to address in our work.\par }{\rtlch\fcs1 \ab\af0 \ltrch\fcs0 \b\insrsid15879383 Learning String Transformations from Examples}{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 . Gulwani [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_conf_popl_Gulwani11 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 2}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] proposed a grammar-based string transformation language to express syntactic transformations. Their method aims to synthesize a desired program including loops and conditions, which together with other functions can express a transformation. Although they designed an efficient algorithm, their method has many performance issues due to the exponential space of transformations that they have to explore. As stated by the author, their algorithm works in practice but it is not guaranteed to work for all cases. This method was extended by Singh et al. [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_journals_pvldb_SinghG12 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 12}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] to support semantic based transformations. Recently, Wu et al. [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_conf_aaai_WuSK12 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 14}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] also proposed a gram-based string transformation learner. Compared to these systems, our approach is simpler and can express all transformations listed in their papers, when the right number of examples is given. \par String transformations have been studied in many other domains as well. For instance, Satta et al. [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_conf_acl_SattaH97 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 11}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ], introduce an original data structure and efficient algorithms that learn some families of transformations that are relevant for part-of-speech tagging and phonological rule systems. Potter\rquote s Wheel [}{\field{\*\fldinst {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 REF BIB_DBLP_conf_vldb_RamanH01 \\* MERGEFORMAT }}{\fldrslt {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 10}}}\sectd \ltrsect\linex0\sectdefaultcl\sftnbj {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 ] is a system that proposes an interactively transformation strategy for data cleaning. They show the evident need of the user interaction in some transformation tasks. Our algorithm can be easily integrated into more complex transformation workflows, as in this process proposed by Potter\rquote s Wheel.\par }\pard\plain \ltrpar\s2\ql \li0\ri0\sb240\sa120\keepn\widctlpar\wrapdefault\faauto\outlinelevel1\rin0\lin0\itap0 \rtlch\fcs1 \ab\af0\afs32 \ltrch\fcs0 \b\fs32\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 7  Conclusions\par }\pard\plain \ltrpar\qj \li0\ri0\sb60\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 We present a novel algorithm to learn string transformation rules from examples. The algorithm is especially useful for non-programmers that in preparation of their data analysis expend a considerable effort on string transformations (e.g. data cleaning). Here, it is presented as a standalone algorithm can be integrate into data processing tools that support the programming-by-example paradigm, such as Microsoft Excel. The empirical investigation indicates this algorithm can learn transformation rules that generalize for a large number of strings, even when a limited number of training examples is given. Additionally, the comparison against a state-of-the-art string transformation algorithm shows 30% improvement in accuracy (in average), indicating that the proposed algorithm is more effective in learning a transformation from a single example, in the majority of the cases. \par }\pard \ltrpar\qj \fi300\li0\ri0\widctlpar\wrapdefault\faauto\rin0\lin0\itap0 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 As future research, we will investigate alternative machine learning approaches to select the rules when a limited set of features and examples are available. The rule selector proposed in this work is satisfactory and ready to be deployed in real applications; however, it may be improved by incorporating state-of-the-art techniques in features selection. Overall, the results achieved in this work can facilitate the data processing tasks of millions of non-programmers (and programmers) that need to do string transformations, in a daily basis. \par }\pard\plain \ltrpar\s52\ql \li450\ri0\widctlpar\wrapdefault\faauto\rin0\lin450\itap0 \rtlch\fcs1 \af0\afs20 \ltrch\fcs0 \fs20\lang1024\langfe1024\cgrid\noproof\langnp1033\langfenp1033 {\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid9849987   }{\rtlch\fcs1 \af0 \ltrch\fcs0 \insrsid15879383 \par }{\*\themedata 504b0304140006000800000021004b9df618000100001c020000130000005b436f6e74656e745f54797065735d2e786d6cac91cb6ac3301045f785fe83d0b6d872ba28a5d8cea28f5d1f8bf40306796c8bda23214d42f2f71d3b0e94124217dd08a499b9f7dc51b9de8f83da614cce53a55779a11592f58da3aed29f9b97ec5eabc4400d0c9eb0d2074c7a5d5f5f959b43c0a4649a52a57be6f0604cb23d8e90721f90a4d2fa3802cb35762680fd820ecd6d51dc19eb899138e34943d7e513b6b01d583defe5f94822e35a3d1efb26ab4a430883b3c0026aa6aaa9cb77018fae41f50191df60942ec382803fcf557e596b47cd2fe0ccb7adb3d878bb1d05339f256f16cf33ac11877401f68cc1b28d5c26e740a977219d1cfe94ea1548d619ff27db22760230f3dfd6df000000ffff0300504b030414000600080000002100a5d6a7e7c0000000360100000b0000005f72656c732f2e72656c73848fcf6ac3300c87ef85bd83d17d51d2c31825762fa590432fa37d00e1287f68221bdb1bebdb4fc7060abb0884a4eff7a93dfeae8bf9e194e720169aaa06c3e2433fcb68e1763dbf7f82c985a4a725085b787086a37bdbb55fbc50d1a33ccd311ba548b63095120f88d94fbc52ae4264d1c910d24a45db3462247fa791715fd71f989e19e0364cd3f51652d73760ae8fa8c9ffb3c330cc9e4fc17faf2ce545046e37944c69e462a1a82fe353bd90a865aad41ed0b5b8f9d6fd010000ffff0300504b0304140006000800000021006b799616830000008a0000001c0000007468656d652f7468656d652f7468656d654d616e616765722e786d6c0ccc4d0ac3201040e17da17790d93763bb284562b2cbaebbf600439c1a41c7a0d29fdbd7e5e38337cedf14d59b4b0d592c9c070d8a65cd2e88b7f07c2ca71ba8da481cc52c6ce1c715e6e97818c9b48d13df49c873517d23d59085adb5dd20d6b52bd521ef2cdd5eb9246a3d8b4757e8d3f729e245eb2b260a0238fd010000ffff0300504b0304140006000800000021009d5c8bbe10070000871d0000160000007468656d652f7468656d652f7468656d65312e786d6cec594f6f1b4514bf23f11d467b6f13274e9a4475aad8b109b469a3d82dea71bc3bf64e33bbb39a1927f10db547242444411ca8c48d03022ab51297f269024550a47e05deccecae77e271e39400153487d63bfb7b6fdefbbd3ff367af5e3b4e183a2442529e3682dae5c5009134e4114d878de076af73692d4052e134c28ca7a4118c890cae6dbefbce55bca162921004f2a9dcc08d20562adb585890210c63799967248577032e12ace0510c1722818f406fc2169616175717124cd300a53801b5b706031a12d4d32a83cd42799bc163aaa41e0899e86ad5c49130d8e8a0a611722c5b4ca043cc1a01cc13f1a31e39560162582a78d10816cd5fb0b07975016fe4424ccd90adc875cc5f2e970b44074b664e31ec9793d63af5f52bdba57e03606a1ad76eb75bed5aa9cf00701882a7d696aace7a67add62c745640f6e7b4eed6e2ca62ddc557f42f4fd9bcde6c3657d6735bac5203b23feb53f8b5c5d5fad6928337208b5f99c2d79b5badd6aa8337208b5f9dc277aeacafd65dbc01c58ca60753681dd04e27d75e42069ced78e16b005f5bcce113146443995d7a8a014fd5ac5c4bf03d2e3a00d04086154d911a67648043c8e21666b42fa89e006f105c796387423935a4e742321434538de0830c43454cf4bd7cf6ddcb674fd0c9fda727f77f3c79f0e0e4fe0f569123b583d36155eac5379ffef1e823f4fb93af5f3cfcdc8f9755fc2fdf7ffcf34f9ff981503e13739e7ff1f8d7a78f9f7ff9c96fdf3ef4c0b704ee57e13d9a10896e9223b4cf1370ccb0e25a4efae27c12bd18d3aac4563a9438c57a168ffeb68a1df4cd3166d8836b1297c13b02da870ff8dee89e637037162395c7dbf1ec7a9c38c05dce59930b2f0bd7f55c159a7ba374e89f5c8caab87d8c0f7d73b770eac4b73dcaa06f529fca564c1c33f7184e151e929428a4dff103423c7cdda5d4e1759786824b3e50e82e454d4cbd94f468dfc9a689d00e4d202e639f81106f879bdd3ba8c999cfeb6d72e822a12a30f318df23cca1f13d3c5238f1a9ece1845509bf8155ec33b23b166115d7960a223d248ca37644a4f4c9dc12e06f25e8d7a175f8c3becbc6898b148a1ef874dec09c5791dbfca015e324f361bb348dabd8f7e501a428467b5cf9e0bbdcad10fd0c71c0e9cc70dfa1c409f7d9dde0361d3a264d1244bf19091d4b68d54e074e68faaa769c4037ceddb9b8760c0df0f9578f3c99f5a636e22d20c157093ba7daef2cdce9a6dbe222a26f7ecfddc6a3748f409a4f2f3c6f5beedb961bfce75beeac7a9eb7d14e7a2bb45dbdbdb19b62b3454e66ee900794b1ae1a3372439a4db2847522eac0a09633a743529e98b2187ee67dddc10d0536324870f521557137c6196cb06b81563294b9eaa144199770b033c35edd1a0f9b74658f852bfac060fb81c46a97477678590f17e782528d596d86e6f0594cb4ac15cc3bd9f2955c29b8fd3a93d5b45173cf5633a69956e7cc56ba0c319c760d064b3661038260db022cafc2f95c4f0d0713cc48a479b76b6f11161385bf2744b9d7d6911847c486c819aeb05933b12b52c85c10404a7942773e364bd680b4b38d3069313b7fe624b95030215997dda96a6269b5b6588a8e1ac1facad24a80429c3582011c49e1679241d0a4deb26136847b9d50099bb567d6a229d289c7ebfeacaac12dc38c8271ca3813526d6319db189a5779a858aa67b2f62fadd475b25d8c0336515fc38ae53548917fcd0a08b51b5a3218905055835d19d1dcd9c7bc13f29122a21b4747a8cf46621f43f88153ed4f4425dc2c9882d60f700da6d936afdcde9a779aeae593c1d971ccb218e7dd525fa3141567e1a6de4a1bcc53c53cf0cd6bbb71eefcaee88abf2857aa69fc3f73452f0770d05f8e740442b8851518e97a6d045ca8984317ca621a7604acfba67740b6c0552abc06f2e12ed8fc2fc8a1fedfd69cd561ca1ace6b6a9f0e91a0b09ca85810b2076dc964df19ca6af9d26355b25c91c9a88ab932b366f7c921613ddd0357750f0e500ca96eba49de060cee74feb9cf7905f5877a8f52ad37a787944ba7ad817f7ae3628b199c3ab597d0f95bf05f9ae859fdacbc112fd6c8aa23fac56497542faac259fcd6d7f3a95ed3847916e0ca5a6b3bd694c74b2b857110c5698f61b0dccf64705d83f43fb0fe511132fb61412fa83dbe0fbd15c17702cb1f82acbea4bb1a64906e90f6571ff63d76d026935665a9cd773e9ab562b1bee08d6a39ef29b2b565f3c4fb9c64979b28773aa7162f92ec9c61876b3b36936a88ece91285a141710e3181315fa4aa1f8d78ff1e047a1baee747cc7e4692193c993ac8f684c9ae3e8fc6f94f26ed826bb34e9f613492a5fb648068745c9c3f4a266c09d94f19c516d9a0b5984eb45270d97768700573bc16b5ab6529bc74b67029616686965d0a9b1b329f02f89095376e7db403bc6db2d66b5d5c05532cfd2b94cd61bc9f32efc9675ecaec41f195817a0dcad4f1ab29cb9902f2a6130f3e450a0c4793aee9bfb0e8d84c3729bbf927000000ffff0300504b0304140006000800000021000dd1909fb60000001b010000270000007468656d652f7468656d652f5f72656c732f7468656d654d616e616765722e786d6c2e72656c73848f4d0ac2301484f78277086f6fd3ba109126dd88d0add40384e4350d363f2451eced0dae2c082e8761be9969bb979dc9136332de3168aa1a083ae995719ac16db8ec8e4052164e89d93b64b060828e6f37ed1567914b284d262452282e3198720e274a939cd08a54f980ae38a38f56e422a3a641c8bbd048f7757da0f19b017cc524bd62107bd5001996509affb3fd381a89672f1f165dfe514173d9850528a2c6cce0239baa4c04ca5bbabac4df000000ffff0300504b01022d00140006000800000021004b9df618000100001c0200001300000000000000000000000000000000005b436f6e74656e745f54797065735d2e786d6c504b01022d0014000600080000002100a5d6a7e7c0000000360100000b00000000000000000000000000310100005f72656c732f2e72656c73504b01022d00140006000800000021006b799616830000008a0000001c000000000000000000000000001a0200007468656d652f7468656d652f7468656d654d616e616765722e786d6c504b01022d00140006000800000021009d5c8bbe10070000871d00001600000000000000000000000000d70200007468656d652f7468656d652f7468656d65312e786d6c504b01022d00140006000800000021000dd1909fb60000001b01000027000000000000000000000000001b0a00007468656d652f7468656d652f5f72656c732f7468656d654d616e616765722e786d6c2e72656c73504b050600000000050005005d010000160b00000000}{\*\colorschememapping 3c3f786d6c2076657273696f6e3d22312e302220656e636f64696e673d225554462d3822207374616e64616c6f6e653d22796573223f3e0d0a3c613a636c724d617020786d6c6e733a613d22687474703a2f2f736368656d61732e6f70656e786d6c666f726d6174732e6f72672f64726177696e676d6c2f323030362f6d61696e22206267313d226c743122207478313d22646b3122206267323d226c743222207478323d22646b322220616363656e74313d22616363656e74312220616363656e74323d22616363656e74322220616363656e74333d22616363656e74332220616363656e74343d22616363656e74342220616363656e74353d22616363656e74352220616363656e74363d22616363656e74362220686c696e6b3d22686c696e6b2220666f6c486c696e6b3d22666f6c486c696e6b222f3e}{\*\latentstyles\lsdstimax276\lsdlockeddef0\lsdsemihiddendef1\lsdunhideuseddef1\lsdqformatdef0\lsdprioritydef99{\lsdlockedexcept \lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdpriority0 \lsdlocked0 Normal;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdlocked0 heading 1;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdlocked0 heading 2;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdlocked0 heading 3;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdlocked0 heading 4;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdlocked0 heading 5;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdlocked0 heading 6;\lsdqformat1 \lsdpriority9 \lsdlocked0 heading 7;\lsdqformat1 \lsdpriority9 \lsdlocked0 heading 8;\lsdqformat1 \lsdpriority9 \lsdlocked0 heading 9;\lsdunhideused0 \lsdlocked0 toc 1;\lsdunhideused0 \lsdlocked0 toc 2;\lsdunhideused0 \lsdlocked0 toc 3;\lsdunhideused0 \lsdlocked0 toc 4;\lsdunhideused0 \lsdlocked0 toc 5;\lsdunhideused0 \lsdlocked0 toc 6;\lsdpriority39 \lsdlocked0 toc 7;\lsdpriority39 \lsdlocked0 toc 8;\lsdpriority39 \lsdlocked0 toc 9;\lsdunhideused0 \lsdlocked0 footnote text;\lsdunhideused0 \lsdlocked0 header;\lsdunhideused0 \lsdlocked0 footer;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdlocked0 caption;\lsdunhideused0 \lsdlocked0 endnote reference;\lsdunhideused0 \lsdlocked0 endnote text;\lsdunhideused0 \lsdlocked0 List;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdlocked0 Title;\lsdunhideused0 \lsdlocked0 Default Paragraph Font;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdpriority11 \lsdlocked0 Subtitle;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdpriority22 \lsdlocked0 Strong;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdpriority20 \lsdlocked0 Emphasis;\lsdsemihidden0 \lsdunhideused0 \lsdpriority59 \lsdlocked0 Table Grid;\lsdunhideused0 \lsdlocked0 Placeholder Text;\lsdunhideused0 \lsdqformat1 \lsdpriority1 \lsdlocked0 No Spacing;\lsdsemihidden0 \lsdunhideused0 \lsdpriority60 \lsdlocked0 Light Shading;\lsdsemihidden0 \lsdunhideused0 \lsdpriority61 \lsdlocked0 Light List;\lsdsemihidden0 \lsdunhideused0 \lsdpriority62 \lsdlocked0 Light Grid;\lsdsemihidden0 \lsdunhideused0 \lsdpriority63 \lsdlocked0 Medium Shading 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority64 \lsdlocked0 Medium Shading 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority65 \lsdlocked0 Medium List 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority66 \lsdlocked0 Medium List 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority67 \lsdlocked0 Medium Grid 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority68 \lsdlocked0 Medium Grid 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority69 \lsdlocked0 Medium Grid 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority70 \lsdlocked0 Dark List;\lsdsemihidden0 \lsdunhideused0 \lsdpriority71 \lsdlocked0 Colorful Shading;\lsdsemihidden0 \lsdunhideused0 \lsdpriority72 \lsdlocked0 Colorful List;\lsdsemihidden0 \lsdunhideused0 \lsdpriority73 \lsdlocked0 Colorful Grid;\lsdsemihidden0 \lsdunhideused0 \lsdpriority60 \lsdlocked0 Light Shading Accent 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority61 \lsdlocked0 Light List Accent 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority62 \lsdlocked0 Light Grid Accent 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority63 \lsdlocked0 Medium Shading 1 Accent 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority64 \lsdlocked0 Medium Shading 2 Accent 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority65 \lsdlocked0 Medium List 1 Accent 1;\lsdunhideused0 \lsdlocked0 Revision;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdpriority34 \lsdlocked0 List Paragraph;\lsdsemihidden0 \lsdunhideused0 \lsdlocked0 Quote;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdpriority30 \lsdlocked0 Intense Quote;\lsdsemihidden0 \lsdunhideused0 \lsdpriority66 \lsdlocked0 Medium List 2 Accent 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority67 \lsdlocked0 Medium Grid 1 Accent 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority68 \lsdlocked0 Medium Grid 2 Accent 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority69 \lsdlocked0 Medium Grid 3 Accent 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority70 \lsdlocked0 Dark List Accent 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority71 \lsdlocked0 Colorful Shading Accent 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority72 \lsdlocked0 Colorful List Accent 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority73 \lsdlocked0 Colorful Grid Accent 1;\lsdsemihidden0 \lsdunhideused0 \lsdpriority60 \lsdlocked0 Light Shading Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority61 \lsdlocked0 Light List Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority62 \lsdlocked0 Light Grid Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority63 \lsdlocked0 Medium Shading 1 Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority64 \lsdlocked0 Medium Shading 2 Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority65 \lsdlocked0 Medium List 1 Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority66 \lsdlocked0 Medium List 2 Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority67 \lsdlocked0 Medium Grid 1 Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority68 \lsdlocked0 Medium Grid 2 Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority69 \lsdlocked0 Medium Grid 3 Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority70 \lsdlocked0 Dark List Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority71 \lsdlocked0 Colorful Shading Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority72 \lsdlocked0 Colorful List Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority73 \lsdlocked0 Colorful Grid Accent 2;\lsdsemihidden0 \lsdunhideused0 \lsdpriority60 \lsdlocked0 Light Shading Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority61 \lsdlocked0 Light List Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority62 \lsdlocked0 Light Grid Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority63 \lsdlocked0 Medium Shading 1 Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority64 \lsdlocked0 Medium Shading 2 Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority65 \lsdlocked0 Medium List 1 Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority66 \lsdlocked0 Medium List 2 Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority67 \lsdlocked0 Medium Grid 1 Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority68 \lsdlocked0 Medium Grid 2 Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority69 \lsdlocked0 Medium Grid 3 Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority70 \lsdlocked0 Dark List Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority71 \lsdlocked0 Colorful Shading Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority72 \lsdlocked0 Colorful List Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority73 \lsdlocked0 Colorful Grid Accent 3;\lsdsemihidden0 \lsdunhideused0 \lsdpriority60 \lsdlocked0 Light Shading Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority61 \lsdlocked0 Light List Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority62 \lsdlocked0 Light Grid Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority63 \lsdlocked0 Medium Shading 1 Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority64 \lsdlocked0 Medium Shading 2 Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority65 \lsdlocked0 Medium List 1 Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority66 \lsdlocked0 Medium List 2 Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority67 \lsdlocked0 Medium Grid 1 Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority68 \lsdlocked0 Medium Grid 2 Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority69 \lsdlocked0 Medium Grid 3 Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority70 \lsdlocked0 Dark List Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority71 \lsdlocked0 Colorful Shading Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority72 \lsdlocked0 Colorful List Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority73 \lsdlocked0 Colorful Grid Accent 4;\lsdsemihidden0 \lsdunhideused0 \lsdpriority60 \lsdlocked0 Light Shading Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority61 \lsdlocked0 Light List Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority62 \lsdlocked0 Light Grid Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority63 \lsdlocked0 Medium Shading 1 Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority64 \lsdlocked0 Medium Shading 2 Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority65 \lsdlocked0 Medium List 1 Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority66 \lsdlocked0 Medium List 2 Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority67 \lsdlocked0 Medium Grid 1 Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority68 \lsdlocked0 Medium Grid 2 Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority69 \lsdlocked0 Medium Grid 3 Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority70 \lsdlocked0 Dark List Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority71 \lsdlocked0 Colorful Shading Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority72 \lsdlocked0 Colorful List Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority73 \lsdlocked0 Colorful Grid Accent 5;\lsdsemihidden0 \lsdunhideused0 \lsdpriority60 \lsdlocked0 Light Shading Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdpriority61 \lsdlocked0 Light List Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdpriority62 \lsdlocked0 Light Grid Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdpriority63 \lsdlocked0 Medium Shading 1 Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdpriority64 \lsdlocked0 Medium Shading 2 Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdpriority65 \lsdlocked0 Medium List 1 Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdpriority66 \lsdlocked0 Medium List 2 Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdpriority67 \lsdlocked0 Medium Grid 1 Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdpriority68 \lsdlocked0 Medium Grid 2 Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdpriority69 \lsdlocked0 Medium Grid 3 Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdpriority70 \lsdlocked0 Dark List Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdpriority71 \lsdlocked0 Colorful Shading Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdpriority72 \lsdlocked0 Colorful List Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdpriority73 \lsdlocked0 Colorful Grid Accent 6;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdpriority19 \lsdlocked0 Subtle Emphasis;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdpriority21 \lsdlocked0 Intense Emphasis;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdpriority31 \lsdlocked0 Subtle Reference;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdpriority32 \lsdlocked0 Intense Reference;\lsdsemihidden0 \lsdunhideused0 \lsdqformat1 \lsdpriority33 \lsdlocked0 Book Title;\lsdpriority37 \lsdlocked0 Bibliography;\lsdqformat1 \lsdpriority39 \lsdlocked0 TOC Heading;}}{\*\datastore 010001000200000010000000584d4c2e5341585265616465722e3500000000000000000000060000d0cf11e0a1b11ae1000000000000000000000000000000003e000300feff090006000000000000000000000001000000010000000000000000100000feffffff00000000feffffff0000000000000000fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffdfffffffeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff5200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000500ffffffffffffffffffffffffec69d9888b8b3d4c859eaf6cd158be0f000000000000000000000000895b05e0d68dce01feffffff00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffff0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffff0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffff0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100010000000000}}